/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/minimum-path-sum
   @Language: C++
   @Datetime: 19-07-01 19:12
   */

class Solution {
public:
	int minPathSum(vector<vector<int>>& grid) {
		if(grid.size()<1) return 0;
		int m=grid.size(), n=grid[0].size();
		for(int i=0; i<m; ++i){
			for(int j=0; j<n; ++j){
				if(i==0 && j==0) continue;
				if(i>0 && j>0) grid[i][j]+=min(grid[i][j-1],grid[i-1][j]);
				else if(i>0) grid[i][j]+=grid[i-1][j];
				else if(j>0) grid[i][j]+=grid[i][j-1];
			}
		}
		return grid[m-1][n-1];
	}
};
